//
// Description: 全排列实现 next_permutation
// Created by Loading on 2021/4/25.
//

#include <bits/stdc++.h>

using namespace std;

void AllPermutation(vector<vector<int>> &res, vector<int> &nums, int k, int m) {
    if (k >= m) {//一次遍历结束，结果加入res
        res.emplace_back(nums);
    } else {
        for (int i = k; i < m; ++i) {
            //遍历到的位置分别和其以及后边位置依次交换
            swap(nums[i], nums[k]);
            //递归向后走
            AllPermutation(res, nums, k + 1, m);
            /* 回溯 */
            swap(nums[i], nums[k]);
        }
    }
}

int main() {
    vector<int> nums = {1, 2, 3, 4};
    vector<vector<int>> res;
    AllPermutation(res, nums, 0, nums.size());
    cout << "全排列一共有：" << res.size() << "种" << endl;
    for (const auto &v : res) {
        for (const auto &x : v) {
            cout << x << " ";
        }
        cout << endl;
    }
}